package mo.daliy;

import java.util.*;

public class L3203 {

    public int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {
        int d1 = treeDiameter(edges1);
        int d2 = treeDiameter(edges2);
        return Math.min(Math.min(d1, d2), (d1+1)/2 + (d2+1)/2 + 1);
    }


    /**
     * 求树的最大直径
     * @param edges
     * @return
     */
    private int treeDiameter(int[][] edges) {
        int n = edges.length + 1;
        Map<Integer, Set<Integer>> edgeMap = new HashMap<>(n);
        for (int[] edge : edges) {
            Set<Integer> targets1 = edgeMap.getOrDefault(edge[0], new HashSet<>());
            targets1.add(edge[1]);
            if (targets1.size() == 1) {
                edgeMap.put(edge[0], targets1);
            }

            Set<Integer> targets2 = edgeMap.getOrDefault(edge[1], new HashSet<>());
            targets2.add(edge[0]);
            if (targets2.size() == 1) {
                edgeMap.put(edge[1], targets2);
            }
        }

        int[] bfs1 = bfs(edgeMap, 0);
        int[] bfs2 = bfs(edgeMap, bfs1[0]);

        return bfs2[1];
    }

    private int[] bfs(Map<Integer, Set<Integer>> edgeMap, int start) {
        int n = edgeMap.size();
        int[] distance = new int[n+1];
        Arrays.fill(distance, -1);
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        distance[start] = 0;

        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            Set<Integer> targets = edgeMap.get(pop);
            if (targets == null) {
                continue;
            }
            for (Integer node : targets) {
                if (distance[node] == -1) {
                    stack.push(node);
                    distance[node] = distance[pop] + 1;
                }
            }
        }

        int maxDis = 0;
        int nodeIdx = 0;
        for (int i = 0; i < n; i++) {
            if (distance[i] > maxDis) {
                maxDis = distance[i];
                nodeIdx = i;
            }
        }

        return new int[]{nodeIdx, maxDis};
    }


    public static void main(String[] args) {
        L3203 l3203 = new L3203();
        int[][] edges1 = new int[][]{{0,1},{0,2},{0,3}};
        int[][] edges2 = new int[][]{{0,1}};
        System.out.println(l3203.minimumDiameterAfterMerge(edges1, edges2));
    }
}
